//
// Created by francklinson on 2022/1/1 AT 14:18.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int maxDistance(vector<int> &colors) {
        unordered_map<int, pair<int, int>> um;
        for (int i = 0; i < colors.size(); ++i) {
            // 有这种颜色了 更新右端
            if (um.count(colors[i])) {
                um[colors[i]].second = i;
            }
                // 没这种颜色  更新左右端
            else {
                um[colors[i]].first = i;
                um[colors[i]].second = i;
            }
        }
        int ans = 0;
        for (auto &p:um) {
            for (auto &q:um) {
                if (p.first != q.first) {
                    ans = max(ans, q.second.second - p.second.first);
                }
            }
        }
        return ans;
    }
};
class Solution2 {
public:
    int maxDistance(vector<int>& colors) {
        int n = colors.size();
        int i, j;
        for(i = 0, j = n-1; i < j; ++i, --j) //由于一定存在不同的颜色，所以当i==j时候一定就是不同的颜色
            if(colors[i] != colors[n-1] || colors[j] != colors[0]) break;
        return j;
    }
};


int main() {
    vector<int> colors{1, 1, 1, 6, 1, 1, 1};
    Solution2 solution;
    cout << solution.maxDistance(colors) << endl;
    return 0;
}

